package DataStructure.linkList;

import utils.CommonUtils;

import java.util.ArrayList;
import java.util.List;

/**
 * 143. 重排链表 https://leetcode.cn/problems/reorder-list/
 * 题目简述：将一个单链表L0 → L1 → … → Ln - 1 → Ln重排为L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
 */
public class ReorderList {


    public static void main(String[] args) {
        ListNode head = CommonUtils.makeNodeList(new int[]{1, 2, 3, 4});
        new ReorderList().reorderList(head);
        System.out.println(head.val);
    }

    /**
     * 思路一：尾递归。去掉头结点和尾结点将剩余len-2长度的链表递归到下一层，递归终止条件为链表长度为2或1，返回上一层的尾结点tail.next并将tail.next置为null
     * ，然后每一层先拿到返回的尾结点tail，然后获取上一层的尾结点nextTail即为tail.next，再把tail插入到head和已重排序的链表中间，最后返回上一层的尾结点nextTail
     */
    public void reorderList(ListNode head) {
        int len = 0;
        ListNode p = head;
        while (p != null) {
            len++;
            p = p.next;
        }
        if (len <= 2) return;
        recur(head, len);
    }

    public ListNode recur(ListNode head, int len) {
        //递归终止条件为链表长度为2或1，将上一层尾结点返回
        if (len == 1) {
            ListNode nextTail = head.next;
            head.next = null;
            return nextTail;
        } else if (len == 2) {
            ListNode nextTail = head.next.next;
            head.next.next = null;
            return nextTail;
        }
        //尾递归获取尾结点tail
        ListNode tail = recur(head.next, len - 2);
        //获取上一层尾结点
        ListNode nextTail = tail.next;
        //将tail插入到head和已重排序的链表中间
        tail.next = head.next;
        head.next = tail;
        return nextTail;
    }

    /**
     * 思路二：先用一个list遍历存储链表所有元素，再遍历链表并从list中获取对应位置元素进行插入，并将最后一个元素的next设为null
     */
    public void reorderList2(ListNode head) {
        ListNode p = head;
        ArrayList<ListNode> nodeArray = new ArrayList<>();
        while(p != null) {
            nodeArray.add(p);
            p = p.next;
        }
        int nSize = nodeArray.size();
        for(int i=0;i < nSize/2 + nSize%2;i++) {
            ListNode node = nodeArray.get(i);
            nodeArray.get(nSize - 1 -i).next = node.next;
            node.next = nodeArray.get(nSize - 1 - i);
        }
        //将最后一个元素的next设为null
        nodeArray.get(nSize/2).next = null;
    }
}
